package C038;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * ClassName: C02
 * Package: C038
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/1/29 20:44
 * @Version 1.0
 * @Since 1.0
 */
public class C02 {
    public static void main(String[] args) {
        int[] arr = {1, 2,3, 1};
        int[] arr2 = {1, 1,1, 1};
        List<List<Integer>> lists = subsetsWithDup(arr2);
        System.out.println(lists);
    }


    public static List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        ArrayList<List<Integer>> ans = new ArrayList<>();
        process(nums, 0, new int[nums.length], 0, ans);
        return ans;
    }

    private static void process(int[] nums, int path, int[] midArr, int index, ArrayList<List<Integer>> ans) {
        if(path == nums.length) {
            ArrayList<Integer> answer = new ArrayList<>();
            for (int i = 0; i < index; i++) {
                answer.add(midArr[i]);
            }
            ans.add(answer);
            return;
        }

        int j = path;
        while(j < nums.length && nums[j] == nums[path] ) {
            j ++;
        }

        // 处理0次
        process(nums, j, midArr, index, ans);
        for (int i = path; i < j; i++) {
            midArr[index++] = nums[i];
            process(nums, j, midArr, index, ans);
        }
    }
}
